package com.wzy.sort8;

import java.util.Arrays;
import java.util.OptionalInt;

/**
 * @author wzy
 * @Date: 2022/1/30 15:44
 * @Description: 桶排序  基数排序
 */
public class JiShuSort {
    public static void main(String[] args) {
        int[] nums = {5, 1, 8, 2, 6, 7, 3, 4};
        radixSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public static void radixSort(int[] arr) {
        int max = findMax(arr, 0, arr.length - 1);
        // 需要遍历的次数由数组最大值位数来决定
        for (int i = 1; max / i > 0; i = i * 10) {
            int[][] buckets = new int[arr.length][10];
            for (int j = 0; j < buckets.length; j++) {
                int num = (arr[j] / i) % 10;
                // 放入桶中
                buckets[j][num] = arr[j];
            }
            // 回收桶中的元素
            int k = 0;
            // 有10个桶子
            for (int j = 0; j < 10; j++) {
                for (int l = 0; l < arr.length; l++) {
                    if (buckets[l][j] != 0) {
                        arr[k++] = buckets[l][j];
                    }
                }
            }
        }
    }


    private static int findMax(int[] arr, int L, int R) {
        if (L == R) {
            return arr[L];
        } else {

            int a = arr[L];
            int b = findMax(arr, L + 1, R);
            if (a > b) {
                return a;
            } else {
                return b;
            }
        }
    }
}
